package tree;

import java.util.*;

/**
 * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行
 * @author le
 */
public class FromTopToBottomPrintBinaryTree
{
    public static void main(String[] args)
    {

    }

    /**
     * 广度优先搜索 BFS通常借用队列的先进先出的特性来实现
     * 将本层的全部结点打印到一行，并将下一层的全部节点加入队列，以此类推
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 建立一个队列 用来存储
        Queue<TreeNode> queue = new LinkedList<>();
        // 创键结果集
        List<List<Integer>> res = new ArrayList<>();
        if(root != null){
            queue.add(root);
        }
        // 当队列不为空时
        while(!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            // 判断队列的大小 从尾部开始遍历
            for (int i = queue.size();i > 0;i--){
                // 开始出队操作
                TreeNode node = queue.poll();
                temp.add(node.val);
                // 判断是否 有左右子树
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
            }
            // 把每一层的添加到返回值当中
            res.add(temp);
        }
        return res;
    }
}
